import node.ThreeNode;

public class Tree {

    //指定节点数，生成完全二叉树
    public static ThreeNode<Integer> creatCompleteBinaryTree(int n, String tag){
        ThreeNode<Integer>[] nodes = new ThreeNode[n];

        for (int i=0;i<n/2;i++){
            if (nodes[i]==null){
                nodes[i] = new ThreeNode<>(i+1,tag);
            }

            //当前节点的左孩子等于2*i + 1
            //当前节点的右孩子等于2*i + 2
            int l=2*i + 1;
            int r=2*i + 2;

            //生成左右子结点
            if (l<n) {
                if (nodes[l]==null){
                    nodes[l] = new ThreeNode<>(l+1,tag);
                }
                nodes[i].left = nodes[l];
                nodes[l].parent=nodes[i];
            }
            if (r<n) {
                if (nodes[r]==null){
                    nodes[r] = new ThreeNode<>(r+1,tag);
                }
                nodes[i].right = nodes[r];
                nodes[r].parent=nodes[i];
            }
        }

        return nodes[0];
    }

    //先序遍历二叉树
    public static void preOrderTraversal(ThreeNode<Integer> root){
        System.out.print(root.data+" ");
        if (root.left!=null){
            preOrderTraversal(root.left);
        }
        if (root.right!=null){
            preOrderTraversal(root.right);
        }
    }
}